package com.itheima.algorithm.recursion_multi;

/**
 * 汉诺塔
 */
public class PascalTriangle {

    /**
     * 使用一维数组记忆法
     * @param row 一维数组
     * @param i 行号
     */
    private static void createRow(int[] row,int i){
        if(i==0){
            row[0] =1;
            return;
        }
        for (int j = i; j > 0; j--) {
            row[j] = row[j]+row[j-1];
        }
    }

    /**
     * 使用二维数组记忆法
     * @param triangle 二维数组
     * @param i 行坐标
     * @param j 列坐标
     * @return
     */
    private static int element1(int[] []triangle, int i,int j){
        if(triangle[i][j]>0){
            // 返回计算后的结果
            return triangle[i][j];
        }
        if(j==0 || i==j){
            triangle[i][j] = 1;
            return 1;
        }
        triangle[i][j] = element1(triangle,i-1,j-1)+element1(triangle,i-1,j);
        return triangle[i][j];
    }

    /**
     * 打印空格
     * @param n 高度
     * @param i 行号
     */
    private static void printSpace(int n,int i){
        int num = 2*(n-1-i);
        for (int j = 0; j < num; j++) {
            System.out.print(" ");

        }
    }

    /**
     * 杨辉三角高度
     * @param n
     */
    public static void print1(int n){
        int [] [] triangle = new int[n][];

        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i+1];
//            printSpace(n,i);
            for (int j = 0; j <=i ; j++) {
                System.out.printf("%-4d",element1(triangle,i,j));
            }
            System.out.println();
        }
    }

    /**
     * 动态规划的应用
     * @param n
     */
    public static void print2(int n){
        int[] row = new int[n];

        for (int i = 0; i < n; i++) {
            createRow(row,i);
//            printSpace(n,i);
            for (int j = 0; j <=i ; j++) {
                System.out.printf("%-4d",row[j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
//        System.out.println(element(4,2));
        print2(5);
    }

}
